package allHot100;

import java.util.HashSet;
import java.util.Set;

/**
 * 128. 最长连续序列
 * 给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
 * 请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
 *
 * 核心解题思路：
 *  1：哈希集合法（时间复杂度O(n)）
 *  核心思想：利用哈希集合（HashSet）快速查找特性，仅从连续序列的起点开始统计长度，避免重复计算.
    关键步骤：
        1：去重：通过hashSet可以对数组进行去重
        2：寻找起点：遍历集合中的每一个元素，若num - 1 不在集合中，则 num 是某个连续序列的起点。
        3：统计长度：从当前起点开始，通过循环连续统计，直到遇到不在集合的元素，然后更新最长子序列的长度。
        4：返回结果：返回最长子序列的长度。
 优化点：每个数字最多被访问两次（存入集合时一次，作为起点扩展时一次），确保时间复杂度为 O(n)
 */
public class L_128 {
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        // 1: 先对数组去重
        for (int num : nums){
            set.add(num);
        }

        int resMax = 0;
        // 2:第二次遍历
        for (int num : nums) {
            // 先找到符合某个连续子序列起点的元素
            // 如果set集合中不包含当前元素的上一个值，则证明当前元素可以作为连续子数组的起点
            if(!set.contains(num-1)){
                // 当前值
                int currentNum = num;
                // 当前子序列的长度
                int currentLength = 1;
                // 循环查找连续值，直到遇到不在集合中的元素
                while (set.contains(currentNum+1)){
                    currentNum++;
                    currentLength++;
                }
                resMax = Math.max(resMax,currentLength);
            }
        }
        return resMax;
    }
}
